package algorithm;


import java.util.Arrays;
import java.util.List;

/**
 * @Author Antony
 * @Since 2018/1/15 11:46
 */
public class BinarySortAndSearchTest {


    /**
     * 二分法查询，需要数列有序
     * 查询数字在数列的位置，如果数字相同，则优先靠前排名。
     */

    public void testBinarySearch(){
        Integer[] array = {2,3,5,6,7,7,9,13,20,25,45,45,80,80,80};
        List<Integer> list = Arrays.asList(array);
        int start = 0;
        int end = list.size()-1;

        int searchNum = 7;
        int rank = binarySearchRank(start, end, list, searchNum);
        //System.out.println(rank);

        Integer[] arr = {2,3,3,3,3,3,4,4,4,4,4,4,6,6,6,6,6};

        //System.out.println(leftSearchRank(arr,2));
        System.out.println(rightSearchRank(arr,4));
    }

    /**
     * 递归方式
     * @param start
     * @param end
     * @param list
     * @param score
     * @return
     */
    private int binarySearchRank(int start, int end, List<Integer> list, int score){
        if(score <= list.get(start)){
            return start;
        }else if(score > list.get(end)){
            return end+1;
        }else if(score == list.get(end)){
            return binarySearchRank(start, end-1, list, score);
        }else if (end-start == 1){
            return end;
        }
        int midIndex = (start+end)%2 == 0 ? (start+end)/2 : (start+end)/2 + 1;
        if(score <= list.get(midIndex)){
            return binarySearchRank(start, midIndex, list, score);
        }else{
            return binarySearchRank(midIndex, end, list, score);
        }
    }

    private int searchRank(Integer[] arr,int key){
        int left = 0;
        int right = arr.length-1;
        int mid;

        while(left<=right){
            mid = (left+right)/2;
            if(key < arr[mid]){
                right = mid-1;
            }else if(arr[mid] < key){
                left = mid+1;
            }else{
                return mid;
            }
        }

        return -1;
    }

    /**
     * 遇到重复元素向左查找
     * @param arr
     * @param key
     * @return
     */
    private int leftSearchRank(Integer[] arr,int key){
        int left = 0;
        int right = arr.length-1;
        int mid;

        while(left<=right){
            mid = (left+right)/2;
            if(key < arr[mid]){
                right = mid-1;
            }else if(arr[mid] < key){
                left = mid+1;
            }else{
                if(right-left <= 1){
                    return left;
                }
                right = mid;
            }
        }
        return -1;
    }

    /**
     * 遇到重复元素向右查找
     * @param arr
     * @param key
     * @return
     */
    private int rightSearchRank(Integer[] arr,int key){
        int left = 0;
        int right = arr.length-1;
        int mid;

        while(left<=right){
            mid = (left+right)/2;
            if(key < arr[mid]){
                right = mid-1;
            }else if(arr[mid] < key){
                left = mid+1;
            }else{
                if(right-left <= 1){
                    return right+1;
                }
                left = mid;
            }
        }

        return -1;
    }
}
